1787G - Colorful Tree Again - CodeForces Solution

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
map <int,int> mp[200005];
struct edge{
    int x,y,w;
};
vector <edge> e[200005];
vector <int> v[200005];
multiset <long long,greater<long long>> ans;
multiset <long long,greater<long long>> s[200005];
long long wt[200005];
int dep[200005],lca[200005],fac[200005],f[200005];
void dfs(int x,int from){
    dep[x]=dep[from]+1;
    for(auto t:v[x])
        if(t!=from)
            dfs(t,x);
}
int main(){
    int T = 1, kase = 0;
    //cin >> T;
    while (T--) {
        int n,q;
        cin>>n>>q;
        for(int i=1,x,y,w,c;i<n;i++){
            scanf("%d%d%d%d",&x,&y,&w,&c);
            e[c].push_back(edge{x,y,w});
            v[x].push_back(y),v[y].push_back(x);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++)
            if(e[i].size()){
                map <int,int> temp,d;
                d[0]=e[i].size()+1;
                long long sum=0;
                int mn=INT_MAX,pos=-1;
                for(auto t:e[i]){
                    d[temp[t.x]]--;
                    temp[t.x]++;
                    d[temp[t.x]]++;
                    d[temp[t.y]]--;
                    temp[t.y]++;
                    d[temp[t.y]]++;
                    if(dep[t.x]<mn) mn=dep[t.x],pos=t.x;
                    if(dep[t.y]<mn) mn=dep[t.y],pos=t.y;
                    sum+=t.w;
                    if(dep[t.x]>dep[t.y]) swap(t.x,t.y);
                    fac[t.y]=i;
                }
                if(d[1]==2&&d[2]==(e[i].size()-1)){
                    lca[i]=pos,s[pos].insert(sum),wt[i]=sum;
                }
                else lca[i]=-1;
                //cout<<i<<" "<<lca[i]<<" "<<wt[i]<<endl;
            }
        for(int i=1;i<=n;i++) if(s[i].size()) ans.insert(*s[i].begin());
        for(int i=1,p,x;i<=q;i++){
            scanf("%d%d",&p,&x);
            f[x]^=1;
            if(!p){
                if(s[x].size()) ans.erase(ans.find(*s[x].begin()));
                if(x!=1&&lca[fac[x]]!=-1){
                    mp[lca[fac[x]]][fac[x]]++;
                    if(mp[lca[fac[x]]][fac[x]]==1){
                        //cout<<"erased"<<" "<<lca[fac[x]]<<endl;
                        if(!f[lca[fac[x]]]) ans.erase(ans.find(*s[lca[fac[x]]].begin()));
                        s[lca[fac[x]]].erase(s[lca[fac[x]]].find(wt[fac[x]]));
                        if(!f[lca[fac[x]]]&&s[lca[fac[x]]].size()) ans.insert(*s[lca[fac[x]]].begin());
                    }
                }
            }
            else{
                if(s[x].size()) ans.insert(*s[x].begin());
                if(x!=1&&lca[fac[x]]!=-1){
                    mp[lca[fac[x]]][fac[x]]--;
                    if(mp[lca[fac[x]]][fac[x]]==0){
                        if(!f[lca[fac[x]]]&&s[lca[fac[x]]].size()) ans.erase(ans.find(*s[lca[fac[x]]].begin()));
                        s[lca[fac[x]]].insert(wt[fac[x]]);
                        if(!f[lca[fac[x]]]) ans.insert(*s[lca[fac[x]]].begin());
                    }
                }
            }
            printf("%lld\n",ans.size()?(*ans.begin()):0);
        }
    }
    return 0;
}